The present invention relates generally to data compression and, more specifically, to a method for increasing data compression ratios by reordering the data bits in a manner that enhances known compression algorithms.
Compression methods condense data to maximize the amount of data that can be stored in a medium having a given storage capacity or to maximize the rate at which data can be transferred in a system having a given bandwidth. Although many compression methods are known in the art, all can be divided into two categories: "lossy," in which some degradation of the original data may occur when the compressed data is decompressed, and "lossless," in which the original data is reproduced exactly when the compressed data is decompressed. Lossy compression methods, such as those promulgated by the Joint Photographic Experts Group (JPEG) and the Motion Picture Experts Group (MPEG), are commonly used in systems that manipulate video and voice data. Lossless compression methods are commonly used in computer systems to maximize the storage capacity of media such as hard disks.
Some lossless compression methods that are specifically for use with storage media such as hard disks increase disk capacity by reordering the data to eliminate wasted space on the disk. However, more general lossless compression methods use run-length encoding (RLE) or a modified form of RLE, such as the Lempel-Ziv-Welch algorithm (LZW) or String Table Compression. In its simplest form, run-length encoding exploits redundancy in the data by locating blocks or runs of a byte having a particular value, and substituting the run with a much smaller number of key bytes that contain both the value of the byte and the number of bytes in the run. To decompress data compressed in this manner, the method examines the key bytes and expands or duplicates the data byte value a number of times equal to the run length. Methods such as RLL and LZW utilize the RLE principle to search for and encode runs consisting of more complex data patterns. The LZW method is described in U.S. Pat. No. 4,558,302, issued to Welch.
Compressing data that have already been compressed may or may not further increase the compression ratio. Performing such iterative or recursive compression using a lossy compression method generally increases the compression ratio, but at the cost of a loss in data quality. Performing recursive compression using a lossless compression method that exploits redundancy in the data, however, generally does not increase the compression ratio. In fact, recursive compression using such a method may actually increase the amount of data.
It would be highly desirable to recursively compress or decompress data using a lossless compression method of a type that exploits redundancy in the data. These problems and deficiencies are clearly felt in the art and are solved by the present invention in the manner described below.